/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓α␈↓ ∧9Notes on paradoxes and self-application

␈↓ ↓H␈↓1.␈α⊂Russell's␈α∂paradox␈α⊂is␈α∂the␈α⊂simplest.␈α⊂ Suppose␈α∂that␈α⊂predicates␈α∂are␈α⊂can␈α∂be␈α⊂applied␈α⊂to␈α∂predicates
␈↓ ↓H␈↓unrestrictedly.  Then we define the predicate ␈↓↓h␈↓ (for ␈↓↓heterological␈↓) by

␈↓ ↓H␈↓1)␈↓ α8  ␈↓↓(∀x)(h(x) ≡ ¬x(x))␈↓.

␈↓ ↓H␈↓Substituting ␈↓↓h␈↓ for ␈↓↓x␈↓ immediately gives

␈↓ ↓H␈↓2)␈↓ α8  ␈↓↓h(h) ≡ ¬h(h)␈↓

␈↓ ↓H␈↓which is already a propositional calculus contradiction.

␈↓ ↓H␈↓2.␈α
Let␈α
us␈α
now␈α
see␈α
how␈α
close␈α
we␈α
can␈α
come␈α
to␈α
translating␈α
Russell's␈α
paradox␈α
into␈α
first␈α
order␈α
logic.␈α
 Let
␈↓ ↓H␈↓␈↓↓α:A␈↓πx␈↓↓A → B␈↓ be a mapping and let ␈↓↓n:B → B␈↓ be a mapping such that

␈↓ ↓H␈↓3)␈↓ α8  ␈↓↓(∀b)(n b ≠ b)␈↓,

␈↓ ↓H␈↓i.e.␈α␈↓↓n␈↓␈αis␈αa␈αmapping␈αwithout␈αa␈αfixed␈αpoint.␈α We␈αshall␈αregard␈αα␈αas␈αan␈α"apply"␈αfunction␈αthat␈αapplies
␈↓ ↓H␈↓an␈α⊃element␈α⊃of␈α⊃␈↓↓A␈↓␈α⊃regarded␈α⊃as␈α⊃a␈α⊃mapping␈α⊂to␈α⊃another␈α⊃element␈α⊃of␈α⊃␈↓↓A␈↓␈α⊃regarded␈α⊃as␈α⊃an␈α⊂argument.
␈↓ ↓H␈↓Therefore, we shall call ␈↓↓␈↓	f␈↓↓:A → B␈↓ representable, if there is ␈↓↓f ε A␈↓ such that

␈↓ ↓H␈↓4)␈↓ α8  ␈↓↓(∀a)(␈↓	f␈↓↓(a) = α(f,a))␈↓.

␈↓ ↓H␈↓For␈α∞example,␈α
if␈α∞␈↓↓A␈↓␈α∞is␈α
taken␈α∞as␈α∞the␈α
set␈α∞of␈α∞S-expressions␈α
in␈α∞LISP␈α∞and␈α
α␈α∞is␈α∞taken␈α
as␈α∞a␈α∞LISP␈α
one-
␈↓ ↓H␈↓argument␈α∞apply␈α
function,␈α∞we␈α∞are␈α
interested␈α∞in␈α
what␈α∞functions␈α∞from␈α
S-expressions␈α∞to␈α∞some␈α
other
␈↓ ↓H␈↓domain are representable.  Consider the function ␈↓	f␈↓␈↓β0␈↓ defined by

␈↓ ↓H␈↓5)␈↓ α8  ␈↓↓␈↓	f␈↓↓␈↓β0␈↓↓(a) = n α(a,a)␈↓.

␈↓ ↓H␈↓We␈αclaim␈αthat␈α␈↓	f␈↓␈↓β0␈↓␈αis␈αnot␈αrepresentable.␈α If␈αit␈α
were␈αrepresented␈αby␈αsome␈αelement␈α␈↓↓a␈↓β0␈↓↓␈↓␈αof␈α␈↓↓A,␈↓␈αwe␈α
would
␈↓ ↓H␈↓have

␈↓ ↓H␈↓6)␈↓ α8  ␈↓↓α(a␈↓β0␈↓↓,a␈↓β0␈↓↓) = ␈↓	f␈↓↓␈↓β0␈↓↓(a␈↓β0␈↓↓) = n α(a␈↓β0␈↓↓,a␈↓β0␈↓↓)␈↓

␈↓ ↓H␈↓which is not possible on account of (3).

␈↓ ↓H␈↓3.␈α⊂Cantor's␈α⊂proof␈α⊂that␈α⊂if␈α⊂a␈α⊂set␈α⊂␈↓↓B␈↓␈α⊂has␈α⊂more␈α⊂than␈α⊂one␈α⊂element,␈α⊂then␈α⊂␈↓↓B␈↓#
A␈↓#␈↓␈α⊂cannot␈α⊂be␈α⊂put␈α⊂in␈α∂1-1
␈↓ ↓H␈↓correspondence␈α
with␈α␈↓↓A,␈↓␈α
can␈αbe␈α
reduced␈αto␈α
the␈α
previous␈αexample.␈α
 Suppose␈αthat␈α
␈↓↓f␈↓␈αtakes␈α
␈↓↓A␈↓␈αinto␈α
␈↓↓B␈↓#
A␈↓#␈↓.
␈↓ ↓H␈↓We then define

␈↓ ↓H␈↓7)␈↓ α8 ␈↓↓α(a1,a2) = f(a1)(a2)␈↓.

␈↓ ↓H␈↓Since ␈↓↓B␈↓ is assumed to have at least two elements, a suitable function ␈↓↓n␈↓ exists and

␈↓ ↓H␈↓8)␈↓ α8 ␈↓↓␈↓	f␈↓↓␈↓β0␈↓↓(a) = n f(a)(a)␈↓,

␈↓ ↓H␈↓and the fact that ␈↓	f␈↓␈↓β0␈↓ is not representable tells us that the mapping ␈↓↓f␈↓ cannot be onto.
␈↓ ↓H␈↓␈↓ εH␈↓ 91


␈↓ ↓H␈↓4. In λ-calculus, we can obtain a fixed point for any λ-expression ␈↓↓f,␈↓ namely

␈↓ ↓H␈↓9)␈↓ α8 ␈↓↓[λx.f(x(x))][λx.f(x(x))] = f[[λx.f(x(x))][λx.f(x(x))]]␈↓,

␈↓ ↓H␈↓where␈α
the␈α
equality␈α
is␈α
established␈α
by␈α
a␈αsingle␈α
λ-conversion␈α
of␈α
the␈α
expression␈α
on␈α
the␈α
left.␈α The␈α
fixed
␈↓ ↓H␈↓point operator itself is therefore given by

␈↓ ↓H␈↓10)␈↓ α8 ␈↓↓Y = λf.[λx.f(x(x))][λx.f(x(x))]␈↓.

␈↓ ↓H␈↓5. The following LlSP expression non-trivially evaluates to itself:

␈↓ ↓H␈↓((LAMBDA␈α
(X)␈α∞(LIST␈α
X␈α
(LIST␈α∞(QUOTE␈α
QUOTE)␈α
X)))␈α∞(QUOTE␈α
(LAMBDA␈α
(X)␈α∞(LIST␈α
X
␈↓ ↓H␈↓(LIST (QUOTE QUOTE) X))))).

␈↓ ↓H␈↓The fact that T and NIL also evaluate to themselves is an anomaly.
␈↓ ↓H␈↓␈↓ εH␈↓ 92


␈↓ ↓H␈↓6.␈αWe␈αshall␈αnow␈αconsider␈αa␈α
translation␈αof␈αthe␈αparadox␈αinto␈αfirst␈α
order␈αlogic.␈α Let␈α␈↓↓F␈↓␈αbe␈αa␈α
set␈αthat
␈↓ ↓H␈↓we␈α
regard␈α
as␈αrepresentations␈α
for␈α
certain␈α
functions␈αfrom␈α
a␈α
set␈α␈↓↓A␈↓␈α
to␈α
a␈α
set␈α␈↓↓B.␈↓␈α
 We␈α
could,␈αfor␈α
example,
␈↓ ↓H␈↓take␈αboth␈α␈↓↓A␈↓␈αand␈α␈↓↓B␈↓␈αas␈αthe␈αset␈αof␈αS-expressions␈αand␈αtake␈α␈↓↓F␈↓␈αas␈αthe␈αS-expression␈αrepresentation␈αof␈αa
␈↓ ↓H␈↓LISP␈α
function.␈α
 Thus␈α
there␈α
is␈α
a␈α
function␈α
α:␈↓↓F ␈↓πx␈↓↓␈α
B → A␈↓␈α
which␈α
could␈α
be␈α
taken␈α
as␈α
the␈α
LISP␈α␈↓↓apply␈↓
␈↓ ↓H␈↓function␈α∂in␈α∂the␈α∂above␈α∂example.␈α∂ We␈α∂will␈α∂call␈α∂a␈α∂function␈α∂␈↓↓␈↓	f␈↓↓:B → A␈↓␈α∂representable␈α∂iff␈α⊂there␈α∂exists
␈↓ ↓H␈↓␈↓↓f ε F␈↓ such that

␈↓ ↓H␈↓11)␈↓ α8  ␈↓↓(∀b)(␈↓	f␈↓↓(b) = α(f,b)␈↓.

␈↓ ↓H␈↓Next␈αlet␈α␈↓↓␈↓	g␈↓↓:F → B␈↓␈αbe␈α1-1,␈αi.e.␈α␈↓	g␈↓␈αrepresents␈αelements␈α
of␈α␈↓↓F␈↓␈αby␈αelements␈αof␈α␈↓↓B.␈↓␈α In␈αthe␈αexample,␈α␈↓	g␈↓␈α
can
␈↓ ↓H␈↓be taken as the identity function.  Finally, let ␈↓↓n:A → A␈↓ satisfy ␈↓↓(∀a)(n(a) ≠ a)␈↓.  Now define

␈↓ ↓H␈↓12)␈↓ α8  ␈↓↓␈↓	f␈↓↓(b) = ␈↓αif␈↓↓ b ε ␈↓	g␈↓↓(F) ␈↓αthen␈↓↓ n(α(␈↓	g␈↓↓␈↓∧-1␈↓↓ b,b)) ␈↓αelse␈↓↓ a␈↓β0␈↓,

␈↓ ↓H␈↓where␈α
␈↓↓a␈↓β0␈↓␈αis␈α
an␈αarbitrary␈α
element␈αof␈α
␈↓↓A.␈↓␈α Suppose␈α
that␈α␈↓	f␈↓␈α
were␈αrepresentable␈α
by␈α␈↓↓f ε F␈↓.␈α
 We␈αwould
␈↓ ↓H␈↓then have

␈↓ ↓H␈↓13)␈↓ α8  ␈↓↓α(f,␈↓	g␈↓↓(f)) = ␈↓	f␈↓↓(␈↓	g␈↓↓(f)) = n(α(␈↓	g␈↓↓␈↓∧-1␈↓↓(␈↓	g␈↓↓(f)),␈↓	g␈↓↓(f))) = n(α(f,␈↓	g␈↓↓(f)))␈↓,

␈↓ ↓H␈↓which is a contradiction, since ␈↓↓n␈↓ has been assumed to have no fixed point.